AVL Tree: Definition

An AVL tree is a self-balancing BST where the heights of the two child subtrees of any node differ by at most one.

Balance Factor (BF)

This property is maintained by tracking a "balance factor" for each node:

$$ \text{BF}(v) = \text{height}(v.\text{left}) - \text{height}(v.\text{right}) $$

For an AVL tree, the balance factor of every node must be in the set \(\{ -1, 0, 1 \}\).

Hover over a node to see its balance factor calculation.